package main.leetcode.clockin.June;

/**
 * 41. 缺失的第一个正数
 *
 * <p>给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
 *
 * <p>示例 1: 输入: [1,2,0] 输出: 3
 *
 * <p>示例 2: 输入: [3,4,-1,1] 输出: 2
 *
 * <p>示例 3: 输入: [7,8,9,11,12] 输出: 1
 *
 * <p>提示：你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
 */
public class day27 {
    public static void main(String[] args) {
        System.out.println(new day27().firstMissingPositive(new int[] {1, 1}));
        System.out.println(new day27().firstMissingPositive(new int[] {7, 8, 9, 10}));
        System.out.println(new day27().firstMissingPositive(new int[] {3, 4, -1, 1}));
        System.out.println(new day27().firstMissingPositive(new int[] {1, 2, 0}));
        System.out.println(
                new day27().firstMissingPositive(new int[] {1, 2, 3, 10, 2147483647, 9}));
    }

    /** 空间复杂度不符合要求 */
    public int firstMissingPositive1(int[] nums) {
        int n = nums.length;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            min = num > 0 ? Math.min(min, num) : min;
        }
        if (min > 1) {
            return 1;
        }
        byte[] bytes = new byte[n];
        for (int num : nums) {
            if (num <= 0 || num - min > n - 1) {
                continue;
            }
            bytes[num - min] = 1;
        }
        for (int i = 0; i < n; ++i) {
            if (bytes[i] == 0) {
                return i + min;
            }
        }
        return n + 1;
    }

    /** 原地哈希 */
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0
                    && nums[i] <= n
                    && /*nums[i] != i + 1*/ nums[nums[i] - 1] != nums[i]) { // 本应该在的地方未被占用
                exch(nums, i, nums[i] - 1);
            }
        }

        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }

    private void exch(int[] nums, int i, int j) {
        nums[i] = nums[i] + nums[j] - (nums[j] = nums[i]);
    }
}
